
/*
 * Copyright (C) 2009-2010 Nayan Kumar K
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this software; see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, MA 02111-1307 USA
 */

#include <iostream>

using namespace std;

int n, W;
int weights[100], values[100];
int cost[6];

void ReadInput(void) 
{
  n = 5;
  W = 6;
  
  weights[1] = 2, values[1] = 12; 
  weights[2] = 1, values[2] = 10;
  weights[3] = 3, values[3] = 20;
  weights[4] = 2, values[4] = 15;
}

int UnboundedKnapSack(void)
{
  for(int i=0; i<W; i++)
    cost[i] = 0;

  for(int j=1; j<n; j++) {
    for(int i=1; i<W; i++) {
      if(i-weights[j] >= 0) {
	if(cost[i] < cost[i-weights[j]]+values[j]) {
	  cost[i] = cost[i-weights[j]] + values[j];
	}
      }
    }
  }

  return cost[5];
}

int main()
{
  ReadInput();

  int max = UnboundedKnapSack();
  cout<<"Max : "<<max<<endl;

  return 0;
}
